package may;

import sun.security.krb5.KrbApRep;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-22 19:58
 * @description： 两种动态规划的解题思路。它们分别是状态转移表法和状态转移方程法。其中，状态转移表法解题思路大致可以概括为，
 * 回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。状态转移方程法的大致思路可以概括为，
 * 找最优子结构-写状态转移方程-将状态转移方程翻译成代码。
 * @modified By：
 * @version:
 */
public class May22 {
    //8皇后问题
//    我们有一个8x8的棋盘,希望往里放8个棋子（皇后）,每个棋子所在的行、列、对角线都不能有另一个棋子。
//    皇后问题就是期望找到所有满足这种要求的放棋子方式。
    //因为同一行只能有一个同一列也只能有一个
    int[] result = new int[8];//全局或成员变量,下标表示行,值表示女王存储在哪一列

    public void cal8queens(int row) { // 调用方式：cal8queens(0);
        if (row == 8) { // 8个棋子都放置好了,打印结果
            printQueens(result);
            return; // 8行棋子都放好了,已经没法再往下递归了,所以就return
        }
        for (int column = 0; column < 8; ++column) { // 每一行都有8中放法
            if (isOk(row, column)) { // 有些放法不满足要求
                result[row] = column; // 第row行的棋子放到了column列
                cal8queens(row + 1);
                // 考察下一行
            }
        }
    }

    private boolean isOk(int row, int column) {//判断row行column列放置是否合适
        int leftup = column - 1, rightup = column + 1;
        for (int i = row - 1; i >= 0; --i) { // 逐行往上考察每一行
            if (result[i] == column) return false; // 第i行的column列有棋子吗？ 往上的每一行的第column列是否有皇后
            if (leftup >= 0) { // 考察左上对角线：第i行leftup列有棋子吗？
                if (result[i] == leftup) return false;
            }
            if (rightup < 8) { // 考察右上对角线：第i行rightup列有棋子吗？
                if (result[i] == rightup) return false;
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

    private void printQueens(int[] result) { // 打印出一个二维矩阵
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; ++column) {
                if (result[row] == column) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值

    // cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；n表示物品个数
// 假设背包可承受重量100,物品个数10,物品重量存储在数组a中,那可以这样调用函数：
// f(0, 0, a, 10, 100)
    public void f(int i, int cw, int[] items, int n, int w) {
        if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
            if (cw > maxW) maxW = cw;
            return;
        }
        f(i + 1, cw, items, n, w);
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候,就不要再装了
            f(i + 1, cw + items[i], items, n, w);
        }
    }

    /**
     * create by: 冯涛滔
     * description: 假设我们有一个n乘以n的矩阵w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角,终止位置在右下角。
     * 我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角,会有很多不同的路径可以走。
     * 我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
     * 这个是回溯算法 这里 l和h写反了
     * create time: 2020-5-22 20:49
     *
     * @params [items, l, h, re] l = 第几列 h = 第几行 re = 现在吃到数值
     * @return void
     */
    public int min = Integer.MAX_VALUE;

    public void qi(int[][] items, int h, int l, int re) {
        re += items[h][l];
        if (h < items.length - 1) { //列还没走到极限就一直尝试向下

            qi(items, h + 1, l, re);
        }
        if (l < items[h].length - 1) {
            qi(items, h, l + 1, re); //向左
        }
        if (h == items.length - 1 || l == items[h].length - 1) {
            if (re < min && h == items.length - 1 && l == items[h].length - 1) {
                min = re;
            }
            return;
        }
    }

    public void qi2(int[][] items) {
        /**
         * create by: 冯涛滔
         * description: 动态规划版(状态转移表法) 每一步都只需要拿到上一步的最小值即可
         * 比如说 items[3][3] 我们只要取items[2][3](头上的)和items[3][2](左边的)最小值即可
         * create time: 2020-5-22 21:57
         * @params [items]
         * @return void
         */
        int[][] res = new int[items.length][items[0].length];
        res[0][0] = items[0][0];
        for (int i = 1; i < res[0].length; i++) {
            res[0][i] = res[0][i - 1] + items[0][i];// 初始化第一行数据
        }
        for (int i = 1; i < res.length; i++) {
            res[i][0] = res[i - 1][0] + items[i][0]; //初始化第一列
        }
        for (int i = 1; i < res.length; i++) {
            for (int j = 1; j < res[i].length; j++) {
                res[i][j] = Math.min(res[i - 1][j], res[i][j - 1]) + items[i][j];
            }
        }
        min = res[res.length - 1][res[0].length - 1];
    }

    private static int[][] matrix =
            {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
    private int n = 4;
    private int[][] mem = new int[4][4];

    //递归加“备忘录”的方式 看不下去了明天再说吧
    public int minDist(int i, int j) { // 调用 minDist(n-1, n-1);
        if (i == 0 && j == 0) {
            return matrix[0][0];
        }
        if (mem[i][j] > 0) {
            return mem[i][j];
        }
        int minLeft = Integer.MAX_VALUE;
        if (j - 1 >= 0) {
            minLeft = minDist(i, j - 1);
        }
        int minUp = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            minUp = minDist(i - 1, j);
        }
        int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
        mem[i][j] = currMinDist;
        return currMinDist;
    }
//    假设我们有几种不同币值的硬币v1，v2，……，vn（单位是元）。如果我们要支付w元，
//    求最少需要多少个硬币。比如，我们有3种	的硬币，1元、3元、5元，我们要支付9元，最少需要3个硬币（3个3元的硬币）。
    public int countMoneyMin(int[] moneyItems, int money) {
        int[] res = new int[money+1];
//        初始化 money是有可能还不到最大面值的
        int startLen = Math.min(money,moneyItems[moneyItems.length-1]);//取一个最小值进行初始化避免溢出
        res[0] = 0;
        for (int i = 1; i <= startLen; i++) {
            int a = i;
            int number = 0;
            for (int j = moneyItems.length-1; j >=0&&a>0; j--) {
                number += a/moneyItems[j];//从最大的开始
                a %= moneyItems[j];
            }
            res[i] = number;
        }
        for (int i = startLen+1; i <= money ; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < moneyItems.length; j++) {
                min = Math.min(res[i-moneyItems[j]],min);
            }
            res[i] = min+1;
        }
        return res[money];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/unique-paths/ 不同路径
     * 状态表法
     * 走到某个位置的走法是他的上面一个位置的走法+左边位置的走法
     * 状态转移公式: i,x个位置的走法 = i-1,x + i,x-1
     * 初始化 第一行和第一列的走法都只有一种
     * create time: 2020-5-25 16:47
     * @params [m, n]
     * @return int
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n ; i++) {//初始化第一行
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++) {//初始化第一列
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {//从第二行开始 减少运算
            for (int j = 1; j < dp[0].length; j++) { //每行从第二哥开始算减少运算
                dp[i][j] = dp[i-1][j] + dp[i][j-1];//上面一格的路数+左边一格的路数
            }
        }
        return dp[m-1][n-1];
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < obstacleGrid.length ; i++) {//初始化第一行
            if(obstacleGrid[0][i]==1){
                dp[0][i] = 0;
            }else{
                dp[0][i] = dp[0][i-1];
            }
        }
        for (int i = 0; i < obstacleGrid[0].length; i++) {//初始化第一列
            if(obstacleGrid[i][0]==1){
                dp[i][0] = 0;
            }else{
                dp[i][0] = dp[i-1][0];
            }
        }
        for (int i = 1; i < dp.length; i++) {//从第二行开始 减少运算
            for (int j = 1; j < dp[0].length; j++) { //每行从第二哥开始算减少运算
                if(obstacleGrid[i][j] == 0){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];//上面一格的路数+左边一格的路数
                }
            }
        }
        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
    public static void main(String[] args) {
        May22 m = new May22();
        int[] moneyItems = {1,3,5};
        System.out.println(m.countMoneyMin(moneyItems, 15));

//        m.cal8queens(0);
//        int[][] items = {{1, 3, 5, 9},
//                {2, 10, 3, 4},
//                {5, 2, 6, 7},
//                {6, 8, 4, 3}};
//        m.qi2(items);
//        m.minDist(m.n - 1, m.n - 1);
//        System.out.println(m.min);
    }

}
